#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <fstream>
#include <set>

using namespace std;

class Solution {
    public:
        string addBinary(string a, string b) {
            int carry = 0;
            string ans;

            reverse(a.begin(), a.end());
            reverse(b.begin(), b.end());
            int i;
            for (i = 0; i < min(a.size(), b.size()) ; i++) {
                int sum = a[i] - '0' + b[i] - '0' + carry;
                if (sum >= 2) {sum -= 2; carry = 1;}
                else carry = 0;
                ans += sum + '0';
            }
            while (i < a.size()) {
                int sum = a[i] - '0' + carry;
                if (sum >= 2) {sum -= 2; carry = 1;}
                else carry = 0;
                ans += sum + '0';
                i++;
            }
            while (i < b.size()) {
                int sum = b[i] - '0' + carry;
                if (sum >= 2) {sum -= 2; carry = 1;}
                else carry = 0;
                ans += sum + '0';
                i++;
            }
            if (carry) ans += '1';
            reverse(ans.begin(), ans.end());
            return ans;
        }
};

//add a better solution here
class Solution {
public:
    string addBinary(string a, string b) {
        string ans;
        reverse(a.begin(), a.end());
        reverse(b.begin(), b.end());
        int i, carry = 0, sum;
        for (i = 0; i < min(a.size(), b.size()); i++) {
            sum = a[i] - '0' + b[i] - '0' + carry;
            carry = sum/2;
            sum %= 2;
            ans.push_back('0' + sum);
        }
        if (i == a.size()) {
            while(i < b.size()) {
                sum = b[i] - '0' + carry;
                carry = sum/2;
                sum %= 2;
                ans.push_back('0' + sum);
                i++;
            }
        }
        if (i == b.size()) {
            while(i < a.size()) {
                sum = a[i] - '0' + carry;
                carry = sum/2;
                sum %= 2;
                ans.push_back('0' + sum);
                i++;
            }
        }        
        if (carry) ans.push_back('1');
        reverse(ans.begin(), ans.end());
        return ans;
    }
};

//add the best code
    string addBinary(string a, string b) {
        string ans;
        int carry = 0;
        reverse(a.begin(), a.end());
        reverse(b.begin(), b.end());
        for (int i = 0; i < a.size() || i < b.size(); i++) {
            int a1 = i >= a.size() ? 0 :a[i] - '0';
            int b1 = i >= b.size() ? 0 :b[i] - '0';
            int sum = a1 + b1 + carry;
            carry = sum/2;
            sum = sum%2;
            ans += sum + '0';
        }   
        if (carry)
            ans += '1';
        reverse(ans.begin(), ans.end());
        return ans;
    }   


//test on 1337 online judge and pass all the test
int main(int argc, char **argv)
{
    Solution mySolution;
    string result;

    cout << "-----------------Test 1--------------------" << endl;
    result = mySolution.addBinary("", "");
    cout << result << endl;

    cout << "-----------------Test 2--------------------" << endl;


    cout << "-----------------Test 3--------------------" << endl;


    cout << "-----------------Test 4--------------------" << endl;


    cout << "-----------------Test 5--------------------" << endl;



}
